package com.learn.algorithm.tree;

import java.util.Arrays;

public class TrieStatic {
    public static int MAX = 15001;
    public static int[] pass = new int[MAX];
    public static int[] end = new int[MAX];
    public static int[][] tree = new int[MAX][26];
    public static int cnt = 1;

    public static void build() {
        cnt = 1;
    }

    public static void insert(String word) {
        int cur = 1;
        pass[cur]++;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
        }
        end[cur]++;
    }

    public static int search(String word) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return end[cur];
    }

    public static void delete(String word) {
        if (search(word) == 0) return;
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (--pass[tree[cur][path]] == 0) {
                return;
            }
            cur = tree[cur][path];
        }
        end[cur]--;
    }

    public static int prefixNumber(String word) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return pass[cur];
    }

    public static void clear() {
        for (int i = 0; i < cnt; i++) {
            Arrays.fill(tree[i], 0);
            pass[i] = 0;
            end[i] = 0;
        }
    }

    public static void main(String[] args) {
        build();
        System.out.println(search("hello"));
        insert("hello");
        insert("hello");
        System.out.println(search("hello"));
        delete("hello");
        System.out.println(search("hello"));


    }
}
